BOJ_18869_멀티버스2

좌표 압축(Coordinate Compression)을 사용해서 푸는 문제
숫자 간 대소 관계만 비교하면 되기 때문에
좌표 압축을 활용해 rank를 구한다

쌍을 구하는 것이기 때문에 같은 랭크가 2 이상이라면
N * (N-1) 을 2로 나눈 것이 정답이 된다

왜냐면 n개가 같은 랭크일 때
nC2의 경우의 수가 나오기 때문!

import sys  
from collections import defaultdict  
  
input = sys.stdin.readline  
  
M, N = map(int, input().split())  
universe = [list(map(int, input().split())) for _ in range(M)]  
count_dict = defaultdict(int)  
  
for cosmo in universe:  
    # 각 숫자의 순위를 매기기  
    sorted_vals = sorted(list(set(cosmo)))  # 중복 제거하고 정렬  
    rank = {val: idx for idx, val in enumerate(sorted_vals)}  
    # 숫자를 순위로 변환  
    pattern = tuple(rank[x] for x in cosmo)  
    count_dict[pattern] += 1  
  
res = 0  
for count in count_dict.values():  
    if count >= 2:  
        res += (count * (count - 1)) // 2  
  
print(res)